package main

import "fmt"

type ListNode struct {
   Val int
   Next *ListNode
}

//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
// 思路
// 其中一个链表取出一个值，插入有序链表中
 //Definition for singly-linked list.

// 每次递归找到最小值，并且连接下一个最小值；

 func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	 if l1 == nil {
		 return l2
	 }else if l2==nil {
		 return l1
	 } else if l1.Val>l2.Val {
	 	l2.Next =mergeTwoLists(l1,l2.Next) // 递归调用状态回归
	 	return l2
	 } else {
	 	 l1.Next=mergeTwoLists(l1.Next,l2) // 递归调用; 在当前的状态中，状态回归了;所以递归调用程序状态在一定的条件下，状态是回归的
	 	 return l1
	 }
 }




/*
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	for	l1 != nil {
		value := l1.Val
		if l2 == nil {
			return l1
		}
		tmp:=l2
		for tmp!= nil{

			if value < tmp.Val{
				var l3 ListNode
				l3.Next=tmp.Next
				l3.Val =tmp.Val
				tmp.Next=&l3
				tmp.Val=value
				break
			}
			tmp=tmp.Next
		}
		if tmp == nil{
			end:=l2
			for end.Next != nil{
				end=end.Next
			}
			var l3 ListNode
			end.Next=&l3
			l3.Val =value
		}
		l1=l1.Next
	}
	if l1== nil {
		return l2
	}
	return l2
}
*/

func main(){

	var ListOne ListNode
	var ListTwo ListNode
	var ListThree ListNode
	ListOne.Val=1
	ListOne.Next=&ListTwo
	ListTwo.Next=&ListThree
	ListTwo.Val=2
	ListThree.Val=4
	var L2One ListNode
	var L2Two ListNode
	var L2Three ListNode
	L2One.Val=1
	L2One.Next=&L2Two
	L2Two.Next=&L2Three
	L2Two.Val=3
	L2Three.Val=4
	fmt.Println(mergeTwoLists(&ListOne,&L2One))
	//mergeTwoLists(&ListOne,&L2One)
	//fmt.Println(ListThree.Next) 链表的默认值 nil
}